package com.cat.chapter053;

/**
 * @author cat
 * @description https://leetcode.cn/problems/steps-to-make-array-non-decreasing/
 * @create 2025/7/25 09:44
 * @since JDK17
 */

public class Solution03 {
    static int N = ((int) (1e5 + 10));
    static int[][] stack = new int[N][2];

    public int totalSteps(int[] nums) {
        int n = nums.length, r = 0, ans = 0, curTurns;
        for (int i = n - 1; i >= 0; i--) {
            curTurns = 0;
            while (r > 0 && stack[r - 1][0] < nums[i]) {    // 小压大
                curTurns = Math.max(stack[--r][1], curTurns + 1);
            }
            stack[r][0] = nums[i];
            stack[r++][1] = curTurns;
            ans = Math.max(ans, curTurns);
        }
        return ans;
    }
}
